class Solution:
    def findDuplicate(self, nums) -> int:
        i=0
        n=len(nums)
        while i<n:
            if nums[i]>n:
                i+=1
                continue
            if nums[nums[i]-1]>n:
                return nums[i]
            if nums[nums[i]-1]==nums[i]:
                if i!=nums[i]-1:
                    return nums[i]
                else:
                    nums[i]+=n
                    i+=1
                    continue
            temp=nums[i]
            nums[i]=nums[temp-1]
            nums[temp-1]=temp+n

s=Solution()
print(s.findDuplicate(
[2,5,9,6,9,3,8,9,7,1]))


# 执行用时：
# 44 ms
# , 在所有 Python3 提交中击败了
# 74.27%
# 的用户
# 内存消耗：
# 16.1 MB
# , 在所有 Python3 提交中击败了
# 50.55%
# 的用户